#ifndef __PRIORITY_QUEUE_HPP__
#define __PRIORITY_QUEUE_HPP__

#include "vector.hpp"

namespace stl_self
{
    template <typename Type>
    struct less
    {
        bool operator()(const Type &left, Type &right)
        {
            return left < right;
        }
    }; // class less

    template <typename Type>
    struct greator
    {
        bool operator()(const Type &left, Type &right)
        {
            return left > right;
        }
    }; // class greator

    template <typename Type, typename Container = stl_self::vector<Type>, typename Compare = less<typename Container::value_type>>
    class priority_queue
    {
    private:
        Container _container;

    private:
        void adjust_up(int child)
        {
            Compare compare;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (compare(_container[parent], _container[child]))
                {
                    std::swap(_container[parent], _container[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void adjust_down(int parent)
        {
            Compare compare;
            int child = parent * 2 + 1;
            while (child < _container.size())
            {
                if (child + 1 < _container.size() && compare(_container[child], _container[child + 1]))
                {
                    child = child + 1;
                }
                if (compare(_container[parent], _container[child]))
                {
                    std::swap(_container[parent], _container[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

    public:
        void push(const Type &value)
        {
            _container.push_back(value);
            adjust_up(_container.size() - 1);
        }

        void pop()
        {
            std::swap(_container[0], _container[_container.size() - 1]);
            _container.pop_back();
            adjust_down(0);
        }

        const Type &top() const { return _container[0]; }
        size_t size() const { return _container.size(); }
        bool empty() const { return _container.empty(); }

        void show()
        {
            for(auto& x : _container)
            {
                std::cout << x << " ";
            }
            std::cout << std::endl;
        }

    }; // class priority_queues
} // namespace stl_self
#endif // #ifndef __PRIORITY_QUEUE_HPP__
